/*
题目: 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

https://leetcode.cn/problems/longest-increasing-subsequence
 */
public class LengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        // 贪心 + 二分
        int n = nums.length;
        // 如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小
        // 表示长度为 i 的最长上升子序列的末尾元素的最小值，用 dLen 记录目前最长上升子序列的长度
        int[] d = new int[n + 1];
        d[0] = nums[0];
        int dLen = 1;
        // 1. 如果nums[i]大于所有元素, 那就d数组增长 2. 找到第一个大于nums[i]的数, 替换

        for (int i = 1; i < n; i++) {
            int binPos = 0; // 二分查找后的元素位置
            int left = 0;
            int right = dLen - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (d[mid] < nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            binPos = right + 1;

            if (binPos == dLen) {
                d[dLen ++] = nums[i];
            } else {
                d[binPos] = nums[i];
            }
        }

        return dLen;
    }
}

